// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2003 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: hash.h,v 1.10 2010-03-11 15:16:40 carzanig Exp $
//
#ifndef HASH_H
#define HASH_H

namespace siena {

/** computes the hash of the string that starts at begin pointer and
 *  ends right before end pointer.
 */
extern unsigned int hash_string(const char* begin, const char *end) throw();

/** computes the hash of the string that starts at begin pointer and
 *  ends with a NULL char ('\0')
 */
extern unsigned int hash_string(const char* s) throw();

//
// INPUT: string = c[1]c[2]c[3] ... c[N]
// OUTPUT: c[1]*X^N + c[2]*X^(N-1) + ... + c[N-1]*X + c[N] mod P
//
template <unsigned int X>
unsigned int phash(const char* b, const char *e) throw() {
    static const unsigned int N = 13;
    static const unsigned int P = (1U << N) - 1U; // 8191 = 2^13 - 1; 
						  // N=17; P=131071 also works 
    register unsigned int h = 0; 
    for ( ; b != e; ++b) {
	h = (X*h + *b) % P;
    }
    return h;
}

//
// INPUT: string = c[1]c[2]c[3] ... c[N]
// OUTPUT: c[1]*X^N + c[2]*X^(N-1) + ... + c[N-1]*X + c[N] mod P
//
class PHash {
private:
    static const unsigned int N = 13;
    static const unsigned int P = (1U << N) - 1U; // 8191 = 2^13 - 1; 
						  // N=17; P=131071 also works 
    unsigned int X;
    unsigned int h; 

public:
    PHash(unsigned int x) : X(x), h(0) {}
    PHash() : X(2), h(0) {}

    void set_base(unsigned int x) throw() { X = x; }

    unsigned int add(const char* b, const char *e) throw() {
	for ( ; b != e; ++b) {
	    h = (X*h + *b) % P;
	}
	return h;
    }

    unsigned int add(int i) throw() {
	h = (X*h + i) % P;
	return h;
    }

    unsigned int add_double(double f) throw() {
	//
	// very quick and dirty hack
	//
	h = (X*h + static_cast<unsigned long>(f)) % P;
	return h;
    }

    unsigned int value() throw() {
	return h;
    }
};

} // end namespace siena

#endif
